package algorithm.difficult;

import sun.applet.Main;
import sun.font.FontRunIterator;

/**
 * 在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。
 *
 * 花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。
 *
 * 给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。
 *
 * 请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。
 */
public class MinTaps1326 {


    /**
     * 贪心
     * @param n
     * @param ranges
     * @return
     */
    public static int minTaps(int n, int[] ranges) {
        int[] maxMost = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            //半径
            int radius = ranges[i];
            if (radius < i) {
                //半径比当前这个节点坐标小。说明i - radius位置能达到的最大坐标为 i + radius
                maxMost[i - radius] = i + radius;
            } else {
                //半径比当前节点下标大，说明可以覆盖到0节点。
                maxMost[0] = Math.max(maxMost[0], i + radius);
            }
        }
        int res = 0;
        //当前最右端点
        int current = 0;
        //下一个最右端点。是会变化的
        int next = 0;
        for (int i = 0; i < n; i++) {
            next = Math.max(next, maxMost[i]);
            //i移动到当前最大节点，需要更新下个最大节点
            if (current == i) {
                //若下个最大和当前最大一样，说明怎么都到不了i+1
                if (next==current) return -1;
                //交换
                current = next;
                res++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        minTaps(5, new int[]{3, 4, 1, 1, 0, 0});
    }
}
